{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Plus Sign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: orderOfLargestPlusSign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大加号标志"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个 <code>n x n</code> 的矩阵&nbsp;<code>grid</code>&nbsp;中，除了在数组&nbsp;<code>mines</code>&nbsp;中给出的元素为&nbsp;<code>0</code>，其他每个元素都为&nbsp;<code>1</code>。<code>mines[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>表示&nbsp;<code>grid[x<sub>i</sub>][y<sub>i</sub>] == 0</code></p>\n",
    "\n",
    "<p>返回 <em>&nbsp;</em><code>grid</code><em> 中包含&nbsp;<code>1</code>&nbsp;的最大的 <strong>轴对齐</strong> 加号标志的阶数</em> 。如果未找到加号标志，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>一个&nbsp;<code>k</code>&nbsp;阶由&nbsp;<em><code>1</code></em>&nbsp;组成的 <strong>“轴对称”加号标志</strong> 具有中心网格&nbsp;<code>grid[r][c] == 1</code>&nbsp;，以及4个从中心向上、向下、向左、向右延伸，长度为&nbsp;<code>k-1</code>，由&nbsp;<code>1</code>&nbsp;组成的臂。注意，只有加号标志的所有网格要求为 <code>1</code> ，别的网格可能为 <code>0</code> 也可能为 <code>1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/plus1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5, mines = [[4, 2]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释: </strong>在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/13/plus2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1, mines = [[0, 0]]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释: </strong>没有加号标志，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= mines.length &lt;= 5000</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt; n</code></li>\n",
    "\t<li>每一对&nbsp;<code>(x<sub>i</sub>, y<sub>i</sub>)</code>&nbsp;都 <strong>不重复</strong>​​​​​​​</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-plus-sign](https://leetcode.cn/problems/largest-plus-sign/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-plus-sign](https://leetcode.cn/problems/largest-plus-sign/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[4,2]]', '1\\n[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "        zeros={(x,y) for x,y in mines}\r\n",
    "        max_k=(n+1)//2\r\n",
    "        ret=0\r\n",
    "        def expand(r,c):\r\n",
    "            if (r,c) in zeros:\r\n",
    "                return 0\r\n",
    "            ret=1\r\n",
    "            while r+ret<n and r-ret>=0 and c+ret<n and c-ret>=0 and (r+ret,c) not in zeros and (r-ret,c) not in zeros and (r,c+ret) not in zeros and (r,c-ret) not in zeros:\r\n",
    "                ret+=1\r\n",
    "            return ret\r\n",
    "        for k in range(max_k,0,-1):\r\n",
    "            rid=[k-1]\r\n",
    "            if n-k!=k-1:\r\n",
    "                rid.append(n-k)\r\n",
    "            for r in rid:\r\n",
    "                for ck in range(max_k,0,-1):\r\n",
    "                    c=ck-1\r\n",
    "                    ret=max(ret,expand(r,c))\r\n",
    "                    if n-ck!=c:\r\n",
    "                        ret=max(ret,expand(r,n-ck))\r\n",
    "            if ret>=k:\r\n",
    "                return ret\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        for x, y in mines:\n",
    "            dp[x][y] = 0\n",
    "        for i in range(n):\n",
    "            left = right = up = down = 0\n",
    "            for j, k in zip(range(n), reversed(range(n))):\n",
    "                left = left + 1 if dp[i][j] else 0\n",
    "                right = right + 1 if dp[i][k] else 0\n",
    "                up = up + 1 if dp[j][i] else 0\n",
    "                down = down + 1 if dp[k][i] else 0\n",
    "                dp[i][j] = min(dp[i][j], left)\n",
    "                dp[i][k] = min(dp[i][k], right)\n",
    "                dp[j][i] = min(dp[j][i], up)\n",
    "                dp[k][i] = min(dp[k][i], down)\n",
    "        return max(max(v) for v in dp)\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        for x, y in mines:\n",
    "            dp[x][y] = 0\n",
    "        for i in range(n):\n",
    "            left = right = up = down = 0\n",
    "            for j, k in zip(range(n), reversed(range(n))):\n",
    "                left = left + 1 if dp[i][j] else 0\n",
    "                right = right + 1 if dp[i][k] else 0\n",
    "                up = up + 1 if dp[j][i] else 0\n",
    "                down = down + 1 if dp[k][i] else 0\n",
    "                dp[i][j] = min(dp[i][j], left)\n",
    "                dp[i][k] = min(dp[i][k], right)\n",
    "                dp[j][i] = min(dp[j][i], up)\n",
    "                dp[k][i] = min(dp[k][i], down)\n",
    "        return max(max(v) for v in dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        if len(mines) == 0:\n",
    "            return n - 1 if n > 1 else 1\n",
    "        self.n = n\n",
    "        self.grid = [[1] * n for _ in range(n)]\n",
    "        for x, y in mines:\n",
    "            self.grid[x][y] = 0\n",
    "\n",
    "        center = 1 if n % 2 == 1 else 2\n",
    "        ans = 0\n",
    "        for k in range((n - 1) // 2, -1, -1):\n",
    "            if ans >= k + 1:\n",
    "                break\n",
    "            maxPlus = 0\n",
    "            for i in range(center):\n",
    "                maxPlus = max(maxPlus, self.getMaxPlus(k, k + i))\n",
    "                maxPlus = max(maxPlus, self.getMaxPlus(k + center - 1, k + i))\n",
    "                maxPlus = max(maxPlus, self.getMaxPlus(k + i, k))\n",
    "                maxPlus = max(maxPlus, self.getMaxPlus(k + i, k + center - 1))\n",
    "\n",
    "            ans = max(ans, maxPlus)\n",
    "\n",
    "            center += 2\n",
    "        return ans\n",
    "\n",
    "    def getMaxPlus(self, x, y):\n",
    "        if self.grid[x][y] == 0:\n",
    "            return 0\n",
    "        for i in range(1, min(x, y) + 1):\n",
    "            if (\n",
    "                x - i < 0\n",
    "                or x + i >= self.n\n",
    "                or y - i < 0\n",
    "                or y + i >= self.n\n",
    "                or self.grid[x - i][y] == 0\n",
    "                or self.grid[x][y - i] == 0\n",
    "                or self.grid[x + i][y] == 0\n",
    "                or self.grid[x][y + i] == 0\n",
    "            ):\n",
    "                return i\n",
    "        return min(x, y) + 1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 2 == Solution().orderOfLargestPlusSign(5, [[4, 2]])\n",
    "    # assert 1 == Solution().orderOfLargestPlusSign(2, [[0, 0], [0, 1], [1, 0]])\n",
    "    # assert 2 == Solution().orderOfLargestPlusSign(\n",
    "    #     5, [[0, 2], [0, 3], [2, 2], [2, 4], [4, 0], [4, 1], [4, 2], [4, 4]]\n",
    "    # )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "\n",
    "        for x, y in mines:\n",
    "\n",
    "            dp[x][y] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            left = right = up = down = 0\n",
    "\n",
    "\n",
    "            for j, k in zip(range(n), reversed(range(n))):\n",
    "\n",
    "                left = left + 1 if dp[i][j] else 0\n",
    "                right = right + 1 if dp[i][k] else 0\n",
    "                up = up + 1 if dp[j][i] else 0\n",
    "                down = down + 1 if dp[k][i] else 0\n",
    "                dp[i][j] = min(dp[i][j], left)\n",
    "                dp[i][k] = min(dp[i][k], right)\n",
    "                dp[j][i] = min(dp[j][i], up)\n",
    "                dp[k][i] = min(dp[k][i], down)\n",
    "\n",
    "        return max(max(v) for v in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "        tables = [[1 for _ in range(n)] for _ in range(n)]\r\n",
    "        for x,y in mines:\r\n",
    "            tables[x][y] = 0\r\n",
    "            \r\n",
    "        max_cross = 0\r\n",
    "        # possisble = n//2 + n%2            \r\n",
    "        # print(tables)\r\n",
    "        # for item in tables:\r\n",
    "        #     print(item)\r\n",
    "        for x in range(n):\r\n",
    "            for y in range(n):\r\n",
    "                max_distance = min(min(x, n-1-x), min(y,n-1-y))\r\n",
    "                if max_distance+1 <= max_cross:\r\n",
    "                    continue\r\n",
    "                if tables[x][y] == 0:\r\n",
    "                    continue\r\n",
    "                if tables[x][y] == 1:\r\n",
    "                    if max_distance == 0:\r\n",
    "                        max_cross = max(1, max_cross)\r\n",
    "                    else:\r\n",
    "                        for distance in range(1, max_distance+1):\r\n",
    "                            flag = 1\r\n",
    "                            if x - distance < 0 or x + distance >= n:\r\n",
    "                                flag = 0\r\n",
    "                            if y - distance < 0 or y + distance >= n:\r\n",
    "                                flag = 0\r\n",
    "                            if tables[x - distance][y] == 0:\r\n",
    "                                flag = 0\r\n",
    "                            if tables[x + distance][y] == 0:\r\n",
    "                                flag = 0\r\n",
    "                            if tables[x][y - distance] == 0:\r\n",
    "                                flag = 0\r\n",
    "                            if tables[x][y + distance] == 0:\r\n",
    "                                flag = 0\r\n",
    "                            if flag:\r\n",
    "                                # print(x, y, distance, max_cross)\r\n",
    "                                max_cross = max(distance+1, max_cross)\r\n",
    "                            else:\r\n",
    "                                break\r\n",
    "        \r\n",
    "        return max_cross"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "        dp = [[n] * n for _ in range(n)]\r\n",
    "        for x, y in mines:\r\n",
    "            dp[x][y] = 0\r\n",
    "        for i in range(n):\r\n",
    "            l = 0\r\n",
    "            for j in range(n):\r\n",
    "                l = 0 if dp[i][j] == 0 else l + 1\r\n",
    "                dp[i][j] = min(dp[i][j], l)\r\n",
    "            r = 0\r\n",
    "            for j in range(n-1, -1, -1):\r\n",
    "                r = 0 if dp[i][j] == 0 else r + 1\r\n",
    "                dp[i][j] = min(dp[i][j], r)\r\n",
    "        for j in range(n):\r\n",
    "            u = 0\r\n",
    "            for i in range(n):\r\n",
    "                u = 0 if dp[i][j] == 0 else u + 1\r\n",
    "                dp[i][j] = min(dp[i][j], u)\r\n",
    "            d = 0\r\n",
    "            for i in range(n-1, -1, -1):\r\n",
    "                d = 0 if dp[i][j] == 0 else d + 1\r\n",
    "                dp[i][j] = min(dp[i][j], d)\r\n",
    "        return max(max(row) for row in dp)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        f = [[n] * n for _ in range(n)]\n",
    "        for x, y in mines:\n",
    "            f[x][y] = 0\n",
    "        for i in range(n):\n",
    "            left = right = top = bottom = 0\n",
    "            for j, k in zip(range(n), reversed(range(n))):\n",
    "                left = left + 1 if f[i][j] else 0\n",
    "                right = right + 1 if f[i][k] else 0\n",
    "                top = top + 1 if f[j][i] else 0\n",
    "                bottom = bottom + 1 if f[k][i] else 0\n",
    "                f[i][j] = min(f[i][j], left)\n",
    "                f[i][k] = min(f[i][k], right)\n",
    "                f[j][i] = min(f[j][i], top)\n",
    "                f[k][i] = min(f[k][i], bottom)\n",
    "        return max(max(row) for row in f)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        for x, y in mines:\n",
    "            dp[x][y] = 0\n",
    "        for i in range(n):\n",
    "            left = right = up = down = 0\n",
    "            for j, k in zip(range(n), reversed(range(n))):\n",
    "                left = left + 1 if dp[i][j] else 0\n",
    "                right = right + 1 if dp[i][k] else 0\n",
    "                up = up + 1 if dp[j][i] else 0\n",
    "                down = down + 1 if dp[k][i] else 0\n",
    "                dp[i][j] = min(dp[i][j], left)\n",
    "                dp[i][k] = min(dp[i][k], right)\n",
    "                dp[j][i] = min(dp[j][i], up)\n",
    "                dp[k][i] = min(dp[k][i], down)\n",
    "        return max(max(v) for v in dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        d = [[math.inf] * n for i in range(n)]\n",
    "        for x,y in mines:\n",
    "            d[x][y]=0\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                # 求左方向\n",
    "                if j==0:\n",
    "                    if d[i][j]!=0:\n",
    "                        cnt =1\n",
    "                        d[i][j] = min(d[i][j], 1)\n",
    "                else:\n",
    "                    if d[i][j] == 0:\n",
    "                        cnt = d[i][j]\n",
    "                    else:\n",
    "                        d[i][j] = min(d[i][j],cnt+1)\n",
    "                        cnt += 1\n",
    "            cnt=0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                # 求右方向\n",
    "                if j==n-1:\n",
    "                    if d[i][j]!=0:\n",
    "                        cnt =1\n",
    "                        d[i][j] = min(d[i][j], 1)\n",
    "                else:\n",
    "                    if d[i][j] == 0:\n",
    "                        cnt = d[i][j]\n",
    "                    else:\n",
    "                        d[i][j] = min(d[i][j], cnt + 1)\n",
    "                        cnt += 1\n",
    "            cnt=0\n",
    "            for j in range(n):\n",
    "                # 求下方向\n",
    "                if j == 0:\n",
    "                    if d[j][i] != 0:\n",
    "                        cnt = 1\n",
    "                        d[j][i]=min(d[j][i],1)\n",
    "                else:\n",
    "                    if d[j][i] == 0:\n",
    "                        cnt = d[j][i]\n",
    "                    else:\n",
    "                        d[j][i] = min(d[j][i], cnt + 1)\n",
    "                        cnt += 1\n",
    "            cnt = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                # 求上方向\n",
    "                if j == n - 1:\n",
    "                    if d[j][i] != 0:\n",
    "                        cnt = 1\n",
    "                        d[j][i] = min(d[j][i], 1)\n",
    "                else:\n",
    "                    if d[j][i] == 0:\n",
    "                        cnt = d[j][i]\n",
    "                    else:\n",
    "                        d[j][i] = min(d[j][i], cnt + 1)\n",
    "                        cnt += 1\n",
    "\n",
    "        return max(d[p][q] for p in range(n) for q in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "        zeros={(x,y) for x,y in mines}\r\n",
    "        f=[[n]*n for _ in range(n)]\r\n",
    "        for i in range(n):\r\n",
    "            #left\r\n",
    "            count=0\r\n",
    "            for j in range(n):\r\n",
    "                if (i,j) in zeros:\r\n",
    "                    count=0\r\n",
    "                else:\r\n",
    "                    count+=1\r\n",
    "                f[i][j]=min(f[i][j],count)\r\n",
    "            # right\r\n",
    "            count=0\r\n",
    "            for j in range(n-1,-1,-1):\r\n",
    "                if (i,j) in zeros:\r\n",
    "                    count=0\r\n",
    "                else:\r\n",
    "                    count+=1\r\n",
    "                f[i][j]=min(f[i][j],count)\r\n",
    "            \r\n",
    "            # top\r\n",
    "            count=0\r\n",
    "            for j in range(n-1,-1,-1):\r\n",
    "                if (j,i) in zeros:\r\n",
    "                    count=0\r\n",
    "                else:\r\n",
    "                    count+=1\r\n",
    "                f[j][i]=min(f[j][i],count)\r\n",
    "            \r\n",
    "            count=0\r\n",
    "            for j in range(n):\r\n",
    "                if (j,i) in zeros:\r\n",
    "                    count=0\r\n",
    "                else:\r\n",
    "                    count+=1\r\n",
    "                f[j][i]=min(f[j][i],count)\r\n",
    "        return max(map(max,f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        used=set(map(tuple,mines))\n",
    "        dp=[[n]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            count=0\n",
    "            #左\n",
    "            for j in range(n):\n",
    "                count=0 if (i,j) in used else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "\n",
    "            count = 0\n",
    "            #右\n",
    "            for j in range(n-1,-1,-1):\n",
    "                count=0 if (i,j) in used else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "\n",
    "\n",
    "        for j in range(n):\n",
    "            count=0\n",
    "            #上\n",
    "            for i in range(n):\n",
    "                count=0 if (i,j) in used else count+1\n",
    "                dp[i][j]=min(count,dp[i][j])\n",
    "\n",
    "            count=0\n",
    "            #下\n",
    "            for i in range(n-1,-1,-1):\n",
    "                count=0 if (i,j) in used else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "        return max(map(max,dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 题意：寻找最大的相同臂长的加号，要求加号内不能有0\n",
    "\n",
    "        # 思路1：暴力超时，以grid[i][j]作为加号中心网格可以得到的最大加号阶数为x\n",
    "        # 遍历所有网格，把每一个网格作为加号中心网格，然后遍历自己的上下左右四个方向，如果四个方向的相邻网格没有\n",
    "        # 0，阶数+1；\n",
    "        # 边界情况：某个方向是否遇到0或者边缘位置\n",
    "        # 遇到边界情况，某个方向的count+0，否则count+1，如果四个方向的count不一致，取最小值为阶数，与ans取最大值\n",
    "        # 向上下走与列有关，向左右走与行有关\n",
    "        # \n",
    "        # ans = -1\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         # 以（i，j）为加号中心\n",
    "        #         if [i, j] in mines:\n",
    "        #             continue\n",
    "        #         left, right, down, up = j, j, i, i\n",
    "        #         # 上下左右取最小\n",
    "        #         while left > 0 and [i, left-1] not in mines:\n",
    "        #             left -= 1\n",
    "        #         while right < n - 1 and [i, right+1] not in mines:\n",
    "        #             right += 1\n",
    "        #         while up > 0 and [up-1, j] not in mines:\n",
    "        #             up -= 1\n",
    "        #         while down < n - 1 and [down+1, j] not in mines:\n",
    "        #             down += 1\n",
    "        #         ans = max(ans, min(j - left, right - j, i - up, down - i))\n",
    "        # return ans + 1 if ans != -1 else 0\n",
    "\n",
    "        # 思路2：动态规划\n",
    "        # 1、确定dp数组的下标及含义\n",
    "        # dp[i][j]表示以[i,j]作为中点的最大加号阶数\n",
    "        # 2、确定递推公式\n",
    "        # dp[i][j]应该与自己的上下左右四个方向有关，所以我们可以分两步走：\n",
    "        # 第一步：只考虑左和上，从左上角往右下角移动，并把所有空格覆盖一次，取左和上的最小阶，\n",
    "        # 此时完成了只考虑左上两个方向的动态规划\n",
    "        # 第二部：只考虑右和下，从右下角往左上角移动，并把所有空格再覆盖一次，取右和下以及自己的\n",
    "        # 最小阶，此时完成右和下两个方向的动态规划\n",
    "        # 完成第一步和第二部后，就实现了上下左右四个方向的动态规划了\n",
    "        # 3、初始化dp数组\n",
    "        # 初始化dp[i][0]以及dp[0][j]，如果格子为1，则初始化为1，如果格子为0，则初始化为0\n",
    "        # 4、确定遍历顺序\n",
    "        # 先从左往右，从上往下遍历，然后从右往左，从下往上遍历\n",
    "        # ans = 0\n",
    "        # dp = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     dp[i][0] = 1 if [i, 0] not in mines else 0\n",
    "        #     ans = max(ans, dp[i][0])\n",
    "        #     dp[i][n-1] = 1 if [i, n-1] not in mines else 0\n",
    "        #     ans = max(ans, dp[i][n-1])\n",
    "        # for j in range(n):\n",
    "        #     dp[0][j] = 1 if [0, j] not in mines else 0\n",
    "        #     ans = max(ans, dp[0][j])\n",
    "        #     dp[n-1][j] = 1 if [n-1, j] not in mines else 0\n",
    "        #     ans = max(ans, dp[n-1][j])\n",
    "\n",
    "        # # 正序遍历\n",
    "        # for i in range(1, n - 1):\n",
    "        #     for j in range(1, n - 1):\n",
    "        #         if [i, j] in mines:\n",
    "        #             continue\n",
    "        #         dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1\n",
    "                \n",
    "        # # 倒序遍历\n",
    "        # for i in range(n - 2, 0, -1):\n",
    "        #     for j in range(n - 2, 0, -1):\n",
    "        #         if [i, j] in mines:\n",
    "        #             continue\n",
    "        #         dp[i][j] = min(min(dp[i + 1][j], dp[i][j + 1]) + 1, dp[i][j])\n",
    "        #         ans = max(ans, dp[i][j])\n",
    "        # return ans\n",
    "\n",
    "        banned = set(map(tuple, mines))\n",
    "        dp = [[n]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            # 往右移动，前缀和\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i,j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # 往左移动\n",
    "            count = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                count = 0 if (i,j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        \n",
    "        for j in range(n):\n",
    "            # 往下移动\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i,j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "\n",
    "            # 往上移动\n",
    "            count = 0\n",
    "            for i in range(n-1, -1, -1):\n",
    "                count = 0 if (i,j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp=[[n]*n for _ in range(n)]\n",
    "        banned=set(map(tuple,mines))\n",
    "        for i in range(n):\n",
    "            count=0\n",
    "            for j in range(n):\n",
    "                count=0 if (i,j) in banned else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "            count=0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                count=0 if (i,j) in banned else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "        for j in range(n):\n",
    "            count=0\n",
    "            for i in range(n):\n",
    "                count=0 if (i,j) in banned else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "            count=0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                count=0 if (i,j) in banned else count+1\n",
    "                dp[i][j]=min(dp[i][j],count)\n",
    "        return max(map(max,dp))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # dp[i][j]表示以(i,j)作为原点在四个方向上的1的最少连续个数\n",
    "        dp = [[n]*n for _ in range(n)]\n",
    "        ban = set(map(tuple,mines))\n",
    "        # 一行\n",
    "        for i in range(n):\n",
    "            count = 0\n",
    "            # 左边的1\n",
    "            for j in range(n):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "            # 右边的1\n",
    "            count = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "        # 一列\n",
    "        for j in range(n):\n",
    "            # 上面的1\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "            # 下面的1\n",
    "            count = 0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "        return max(map(max,dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 题意：寻找最大的相同臂长的加号，要求加号内不能有0\n",
    "\n",
    "        # 思路1：暴力，以grid[i][j]作为加号中心网格可以得到的最大加号阶数为x\n",
    "        # 遍历所有网格，把每一个网格作为加号中心网格，然后遍历自己的上下左右四个方向，如果四个方向的相邻网格没有\n",
    "        # 0，阶数+1；\n",
    "        # 边界情况：某个方向是否遇到0或者边缘位置\n",
    "        # 遇到边界情况，某个方向的count+0，否则count+1，如果四个方向的count不一致，取最小值为阶数，与ans取最大值\n",
    "        # 向上下走与列有关，向左右走与行有关\n",
    "        # 不考虑中心点在边上\n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "        # 思路1：动态规划\n",
    "        # 1、确定dp数组的下标及含义\n",
    "        # \n",
    "\n",
    "\n",
    "        # 2、确定递推公式\n",
    "\n",
    "        # 3、初始化dp数组\n",
    "\n",
    "        # 4、确定遍历顺序\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]\n",
    "        s = set()\n",
    "        for mine in mines:\n",
    "            s.add(n * mine[0] + mine[1])\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):#left\n",
    "                cnt = 0 if n * i + j in s else cnt + 1\n",
    "                dp[i][j] = cnt\n",
    "            cnt = 0\n",
    "            for j in range(n - 1, -1, -1):#right\n",
    "                cnt = 0 if n * i + j in s else cnt + 1\n",
    "                dp[i][j] = min(dp[i][j], cnt)\n",
    "        for j in range(n):\n",
    "            cnt = 0\n",
    "            for i in range(n):#up\n",
    "                cnt = 0 if n * i + j in s else cnt + 1\n",
    "                dp[i][j] = min(dp[i][j], cnt)\n",
    "            cnt = 0\n",
    "            for i in range(n - 1, -1, -1):#down\n",
    "                cnt = 0 if n * i + j in s else cnt + 1\n",
    "                dp[i][j] = min(dp[i][j], cnt)\n",
    "                res = max(dp[i][j], res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        banned = set(map(tuple,mines))\n",
    "        dp = [[n]*n for _ in range(n)]\n",
    "        #left and right\n",
    "        for r in range(n):\n",
    "            count = 0\n",
    "            #left\n",
    "            for c in range(n):\n",
    "                count = 0 if (r,c) in banned else count+1\n",
    "                dp[r][c] = min(dp[r][c],count)\n",
    "            count = 0\n",
    "            #right\n",
    "            for c in range(n-1,-1,-1):\n",
    "                count = 0 if (r,c) in banned else count+1\n",
    "                dp[r][c] = min(dp[r][c],count)\n",
    "        #up and down\n",
    "        for c in range(n):\n",
    "            count = 0\n",
    "            #down\n",
    "            for r in range(n):\n",
    "                count = 0 if (r,c) in banned else count+1\n",
    "                dp[r][c] = min(dp[r][c],count)\n",
    "            count = 0\n",
    "            #up\n",
    "            for r in range(n-1,-1,-1):\n",
    "                count = 0 if (r,c) in banned else count+1\n",
    "                dp[r][c] = min(dp[r][c],count)\n",
    "        return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "      dp = [[n] * n for _ in range(n)]\n",
    "      mines = set(map(tuple, mines))\n",
    "\n",
    "      def update(i, j, m):\n",
    "        m = 0 if (i, j) in mines else m + 1\n",
    "        dp[i][j] = min(dp[i][j], m)\n",
    "        return m\n",
    "\n",
    "      for i in range(n):\n",
    "        m = 0\n",
    "        for j in range(n):\n",
    "          m = 0 if (i, j) in mines else m + 1\n",
    "          dp[i][j] = min(dp[i][j], m)\n",
    "\n",
    "        m = 0\n",
    "        for j in range(n - 1, -1, -1):\n",
    "          m = 0 if (i, j) in mines else m + 1\n",
    "          dp[i][j] = min(dp[i][j], m)\n",
    "\n",
    "      for j in range(n):\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "          m = 0 if (i, j) in mines else m + 1\n",
    "          dp[i][j] = min(dp[i][j], m)\n",
    "\n",
    "        m = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "          m = 0 if (i, j) in mines else m + 1\n",
    "          dp[i][j] = min(dp[i][j], m)\n",
    "\n",
    "      return max(map(max, dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[inf]*n for _ in range(n)]\n",
    "        ban = set(map(tuple,mines))\n",
    "        # 枚举行\n",
    "        for i in range(n):\n",
    "            # 枚举左\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "            # 枚举右\n",
    "            count = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "        # 枚举列\n",
    "        for j in range(n):\n",
    "            # 枚举上\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "            # 枚举下\n",
    "            count = 0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                count = 0 if (i,j) in ban else count+1\n",
    "                dp[i][j] = min(dp[i][j],count)\n",
    "        return max(map(max,dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 还是可以用动态规划，像这种的动态规划一般出现在相邻关系非常紧密的情况下，也就是左右有相互关系。\n",
    "        # 动态规划的话，需要添加四个矩阵，每个矩阵代表着上下左右四个方向1以当前位置为终点能辐射多长的路，最终答案就是四个里面最小的，如果有零，那么辐射为0.写一个函数，把矩阵转置一下就能得到。\n",
    "        # 类似网格，边界，或者特定形状，都是用动态规划来做，动态规划一定是去找他们彼此之间的相互关系。\n",
    "        '''\n",
    "\n",
    "        ans = 0\n",
    "        def find(mines):\n",
    "            dp1 = [[0]*n for _ in range(n)]\n",
    "            dp2 = [[0]*n for _ in range(n)]\n",
    "            dp = [[0]*n for _ in range(n)]\n",
    "            \n",
    "            for i in range(n):\n",
    "                dp1[i][0] = 1 if [i,0] not in mines else 0\n",
    "                dp2[i][0] = 1 if [i,0] not in mines else 0\n",
    "                dp[i][0] = 1 if [i,0] not in mines else 0\n",
    "                dp1[0][i] = 1 if [0,i] not in mines else 0\n",
    "                dp2[0][i] = 1 if [0,i] not in mines else 0\n",
    "                dp[0][i] = 1 if [0,i] not in mines else 0\n",
    "\n",
    "            for i in range(1,n):\n",
    "                for j in range(1,n):\n",
    "                    if [i,j] in mines:\n",
    "                        dp1[i][j], dp2[i][j] = 0, 0\n",
    "                    else:\n",
    "                        dp1[i][j] = dp1[i-1][j]+1\n",
    "                        dp2[i][j] = dp2[i][j-1]+1\n",
    "                    dp[i][j] = min(dp1[i][j], dp2[i][j])\n",
    "\n",
    "            print(dp)\n",
    "            print(mines)\n",
    "            return dp\n",
    "        \n",
    "        mat1 = find(mines)\n",
    "        mines2 = [[n-i-1,n-j-1] for i,j in mines]\n",
    "        mat2 = find(mines2)\n",
    "       # print(mat2)\n",
    "        mat2.reverse()      # 这个错误犯了好几次了，两边都reverse只能得到中心对称，但是不是\n",
    "        for row in mat2:\n",
    "            row.reverse()\n",
    "        \n",
    "        print(mat1, mat2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, min(mat1[i][j], mat2[i][j]))\n",
    "        return ans\n",
    "        '''\n",
    "       \n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "    #     tables = [[1 for _ in range(n)] for _ in range(n)]\r\n",
    "    #     for x,y in mines:\r\n",
    "    #         tables[x][y] = 0\r\n",
    "            \r\n",
    "    #     max_cross = 0\r\n",
    "    #     # possisble = n//2 + n%2            \r\n",
    "    #     # print(tables)\r\n",
    "    #     # for item in tables:\r\n",
    "    #     #     print(item)\r\n",
    "    #     for x in range(n):\r\n",
    "    #         for y in range(n):\r\n",
    "    #             max_distance = min(min(x, n-1-x), min(y,n-1-y))\r\n",
    "    #             if max_distance+1 <= max_cross:\r\n",
    "    #                 continue\r\n",
    "    #             if tables[x][y] == 0:\r\n",
    "    #                 continue\r\n",
    "    #             if tables[x][y] == 1:\r\n",
    "    #                 if max_distance == 0:\r\n",
    "    #                     max_cross = max(1, max_cross)\r\n",
    "    #                 else:\r\n",
    "    #                     for distance in range(1, max_distance+1):\r\n",
    "    #                         flag = 1\r\n",
    "    #                         if x - distance < 0 or x + distance >= n:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if y - distance < 0 or y + distance >= n:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if tables[x - distance][y] == 0:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if tables[x + distance][y] == 0:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if tables[x][y - distance] == 0:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if tables[x][y + distance] == 0:\r\n",
    "    #                             flag = 0\r\n",
    "    #                         if flag:\r\n",
    "    #                             # print(x, y, distance, max_cross)\r\n",
    "    #                             max_cross = max(distance+1, max_cross)\r\n",
    "    #                         else:\r\n",
    "    #                             break\r\n",
    "        \r\n",
    "    #     return max_cross\r\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\r\n",
    "        dp = [[n]*n for _ in range(n)]\r\n",
    "        for i, j in mines:\r\n",
    "            dp[i][j] = 0\r\n",
    "            \r\n",
    "        max_cross = 0\r\n",
    "        # possisble = n//2 + n%2            \r\n",
    "        # print(tables)\r\n",
    "        # for item in tables:\r\n",
    "        #     print(item)\r\n",
    "        \r\n",
    "        for i in range(n):\r\n",
    "            counter = 0\r\n",
    "            for j in range(n):\r\n",
    "                counter = counter + 1 if dp[i][j] else 0\r\n",
    "                dp[i][j] = min(dp[i][j], counter)\r\n",
    "        \r\n",
    "        for i in range(n):\r\n",
    "            counter = 0\r\n",
    "            for j in range(n-1, -1, -1):\r\n",
    "                counter = counter + 1 if dp[i][j] else 0\r\n",
    "                dp[i][j] = min(dp[i][j], counter)\r\n",
    "        \r\n",
    "        for j in range(n):\r\n",
    "            counter = 0\r\n",
    "            for i in range(n):\r\n",
    "                counter = counter + 1 if dp[i][j] else 0\r\n",
    "                dp[i][j] = min(dp[i][j], counter)\r\n",
    "        \r\n",
    "        for j in range(n):\r\n",
    "            counter = 0\r\n",
    "            for i in range(n-1, -1, -1):\r\n",
    "                counter = counter + 1 if dp[i][j] else 0\r\n",
    "                dp[i][j] = min(dp[i][j], counter)\r\n",
    "        \r\n",
    "\r\n",
    "        return max(max(v) for v in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1] * n for _ in range(n)]\n",
    "        \n",
    "        # 将矿石位置标记为0\n",
    "        for mine in mines:\n",
    "            grid[mine[0]][mine[1]] = 0\n",
    "\n",
    "        # 初始化dp数组，分别表示左、右、上、下四个方向的最大连续1的长度\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            left,right = 0,0\n",
    "            for j in range(n):\n",
    "                left = 0 if grid[i][j]==0 else left+1\n",
    "                dp[i][j] = left\n",
    "            for j in range(n-1,-1,-1):\n",
    "                right = 0 if grid[i][j]==0 else right+1\n",
    "                dp[i][j] = min(dp[i][j],right)\n",
    "        for j in range(n):\n",
    "            top,down = 0,0\n",
    "            for i in range(n):\n",
    "                top = 0 if grid[i][j]==0 else top+1\n",
    "                dp[i][j] = min(dp[i][j],top)\n",
    "            for i in range(n-1,-1,-1):\n",
    "                down = 0 if grid[i][j]==0 else down+1\n",
    "                dp[i][j] = min(dp[i][j],down)\n",
    "        max_len = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                max_len = max(max_len,dp[i][j])\n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1] * n for _ in range(n)]\n",
    "        \n",
    "        # 将矿石位置标记为0\n",
    "        for mine in mines:\n",
    "            grid[mine[0]][mine[1]] = 0\n",
    "\n",
    "        # 初始化dp数组，分别表示左、右、上、下四个方向的最大连续1的长度\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            left, right, up, down = 0, 0, 0, 0\n",
    "            for j in range(n):\n",
    "                # 从左往右更新dp数组\n",
    "                left = 0 if grid[i][j] == 0 else left + 1\n",
    "                dp[i][j] = left\n",
    "\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                # 从右往左更新dp数组\n",
    "                right = 0 if grid[i][j] == 0 else right + 1\n",
    "                dp[i][j] = min(dp[i][j], right)\n",
    "\n",
    "        # 更新dp数组，从上往下和从下往上\n",
    "        for j in range(n):\n",
    "            up, down = 0, 0\n",
    "            for i in range(n):\n",
    "                # 从上往下更新dp数组\n",
    "                up = 0 if grid[i][j] == 0 else up + 1\n",
    "                dp[i][j] = min(dp[i][j], up)\n",
    "\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                # 从下往上更新dp数组\n",
    "                down = 0 if grid[i][j] == 0 else down + 1\n",
    "                dp[i][j] = min(dp[i][j], down)\n",
    "\n",
    "        max_order = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                max_order = max(max_order, dp[i][j])\n",
    "\n",
    "        return max_order\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp = [[n] * n for _ in range(n)]\n",
    "        banned = set(map(tuple, mines))\n",
    "        print(banned)\n",
    "        print(dp)\n",
    "        for i in range(n):\n",
    "            # left\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # right\n",
    "            count = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        for j in range(n):\n",
    "            # up\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "            # down\n",
    "            count = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                count = 0 if (i, j) in banned else count + 1\n",
    "                dp[i][j] = min(dp[i][j], count)\n",
    "        return max(map(max, dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "       left = [[0] * n for _ in range(n)]\n",
    "       up = [[0] * n for _ in range(n)]\n",
    "       s = set()\n",
    "       for x, y in mines:\n",
    "          s.add((x, y))\n",
    "       for i in range(n):\n",
    "          for j in range(n):\n",
    "             if j == 0:\n",
    "                left[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                left[i][j] = 0 if (i, j) in s else left[i][j - 1] + 1\n",
    "             if i == 0:\n",
    "                up[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                up[i][j] = 0 if (i, j) in s else up[i - 1][j] + 1\n",
    "       res = 0\n",
    "       down = [0] * n\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          right = 0\n",
    "          for j in range(n - 1, -1, -1):\n",
    "             if j == n - 1:\n",
    "                right = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                right = 0 if (i, j) in s else right + 1\n",
    "             if i == n - 1:\n",
    "                down[j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                down[j] = 0 if (i, j) in s else down[j] + 1\n",
    "             res = max(res, min(min(left[i][j], right), min(up[i][j], down[j])))\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "       left = [[0] * n for _ in range(n)]\n",
    "       up = [[0] * n for _ in range(n)]\n",
    "       s = set()\n",
    "       for x, y in mines:\n",
    "          s.add((x, y))\n",
    "       for i in range(n):\n",
    "          for j in range(n):\n",
    "             if j == 0:\n",
    "                left[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                left[i][j] = 0 if (i, j) in s else left[i][j - 1] + 1\n",
    "             if i == 0:\n",
    "                up[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                up[i][j] = 0 if (i, j) in s else up[i - 1][j] + 1\n",
    "       res = 0\n",
    "      #  right = [[0] * n for _ in range(n)]\n",
    "       down = [[0] * n for _ in range(n)]\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          right = 0\n",
    "          for j in range(n - 1, -1, -1):\n",
    "             if j == n - 1:\n",
    "                right = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                right = 0 if (i, j) in s else right + 1\n",
    "             if i == n - 1:\n",
    "                down[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                down[i][j] = 0 if (i, j) in s else down[i + 1][j] + 1\n",
    "             res = max(res, min(min(left[i][j], right), min(up[i][j], down[i][j])))\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 每个嗲 向四个正方向同时找 1 成功一次则 加号长 +1 \n",
    "        # 优化: 从中间向两边 一圈圈 寻找点 每次\n",
    "        arr = [[1 for _ in range(n)] for _ in range(n)]\n",
    "        for i, j in mines:\n",
    "            arr[i][j] = 0\n",
    "        # n = 3 时 寻找两次 入口点为 1-1 即 range(1,2)\n",
    "        # n = 4 时 寻找两次 入口点为 1-2 即 range(1,3)\n",
    "        # 那么 入口点为 l=(n-1)//2 , r=n//2\n",
    "        # 由于公式只需计算一次 ，之后则为 l-1 r+1 即可表示外圈，完成层级提取\n",
    "        @cache\n",
    "        def dfs(x, k):\n",
    "            i = 0\n",
    "            while x+i < n and x-i >= 0 and k+i < n and k-i >= 0 and arr[x+i][k] and arr[x-i][k] and arr[x][k+i] and arr[x][k-i]:\n",
    "                i += 1\n",
    "            return i\n",
    "        l, r = (n-1) // 2, n // 2\n",
    "        ans = 0\n",
    "        while l >= 0:\n",
    "            # 顺时针或者逆时针 旋转 90 ° 重复三次 即可表示外圈\n",
    "            # (i,j) -> (n-i,j) -> (n-i,n-j) -> (j,i)  表示错了 这数学水平 差的 啧啧称奇\n",
    "            if ans >= l+1: return ans  # 如果不进行剪枝，则会在后面生成更小的 并立即被 return 导致出错\n",
    "            if l == r:\n",
    "                i = dfs(l, r)\n",
    "                ans = max(ans, i)\n",
    "                if i == l+1: return l+1\n",
    "            res = [[l, z] for z in range(l, r)]\n",
    "            for x,k in res:\n",
    "                # print((x,k),(k,n-x-1),(n-x-1,n-k-1),(n-k-1,x))\n",
    "                # 达到正在被遍历时会生成的最大长度，由于在一圈圈的压缩，符合最大生成后就不可能会有更大，贪心策略\n",
    "                a, b, c, d = dfs(x,k), dfs(k,n-x-1), dfs(n-x-1,n-k-1), dfs(n-k-1,x)\n",
    "                ans = max(ans, a, b, c, d)\n",
    "                if dfs(x, k)==l+1 or dfs(x,n-x-1)==l+1 or dfs(n-x-1, n-k-1)==l+1 or dfs(n-k-1, x)==l+1: return l+1 \n",
    "            l, r = l-1, r+1\n",
    "        return ans  # 一个符合条件的都没有 那只剩下最不可能的 即没有 1 的情况 否则在遍历到最后一次时"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid=[[1]*n for _ in range(n)]\n",
    "        for i,j in mines:\n",
    "            grid[i][j]=0\n",
    "        row_pre=[[0]*(n+1) for _ in range(n+1)]\n",
    "        col_pre=[[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                row_pre[i][j]=row_pre[i][j-1]+grid[i-1][j-1]\n",
    "        for j in range(1,n+1):\n",
    "            for i in range(1,n+1):\n",
    "                col_pre[i][j]=col_pre[i-1][j]+grid[i-1][j-1]\n",
    "        def check(r):\n",
    "            for i in range(r,n+2-r):\n",
    "                for j in range(r,n+2-r):\n",
    "                    delta_x=row_pre[i][j+r-1]-row_pre[i][j-r]\n",
    "                    #print(i,j,r,'|',j+r-1,j-r,'|',row_pre[i][j+r-1],row_pre[i][j-r],'dx',delta_x)\n",
    "                    delta_y=col_pre[i+r-1][j]-col_pre[i-r][j]\n",
    "                    #print(i,j,r,'|',i+r-1,i-r,'|',col_pre[i+r-1][j],col_pre[i-r][j],'dy',delta_y)\n",
    "                    if delta_x==delta_y==2*r-1:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=1,n//2+1\n",
    "        ans=0\n",
    "        #print('lr',left,right)\n",
    "        while left<=right:\n",
    "            #print('l,r',left,right)\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid=[[1]*n for _ in range(n)]\n",
    "        for i,j in mines:\n",
    "            grid[i][j]=0\n",
    "        row_pre=[[0]*(n+1) for _ in range(n+1)]\n",
    "        col_pre=[[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                row_pre[i][j]=row_pre[i][j-1]+grid[i-1][j-1]\n",
    "        for j in range(1,n+1):\n",
    "            for i in range(1,n+1):\n",
    "                col_pre[i][j]=col_pre[i-1][j]+grid[i-1][j-1]\n",
    "        def check(r):\n",
    "            for i in range(r,n+2-r):\n",
    "                for j in range(r,n+2-r):\n",
    "                    delta_x=row_pre[i][j+r-1]-row_pre[i][j-r]\n",
    "                    delta_y=col_pre[i+r-1][j]-col_pre[i-r][j]\n",
    "                    if delta_x==delta_y==2*r-1:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=1,n//2+1\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 定义dpx[i][j][k]为以[i,j]为中心，朝着方向x能延展的最大长度\n",
    "        dpl = [[1]*n for _ in range(n)] # 左\n",
    "        dpr = [[1]*n for _ in range(n)] # 右\n",
    "        dpt = [[1]*n for _ in range(n)] # 上\n",
    "        dpb = [[1]*n for _ in range(n)] # 下\n",
    "\n",
    "        # 把地雷坐标放上去\n",
    "        for mi, mj in mines:\n",
    "            dpl[mi][mj] = 0\n",
    "            dpr[mi][mj] = 0\n",
    "            dpt[mi][mj] = 0\n",
    "            dpb[mi][mj] = 0\n",
    "\n",
    "        # 计算左边和右边方向的长度\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                if dpl[i][j] != 0: dpl[i][j] += dpl[i][j-1]\n",
    "\n",
    "            for j in range(n-2, -1, -1):\n",
    "                if dpr[i][j] != 0: dpr[i][j] += dpr[i][j+1]\n",
    "\n",
    "        # 计算上面和下面方向的长度\n",
    "        for j in range(n):\n",
    "            for i in range(1, n):\n",
    "                if dpt[i][j] != 0: dpt[i][j] += dpt[i-1][j]\n",
    "\n",
    "            for i in range(n-2, -1, -1):\n",
    "                if dpb[i][j] != 0: dpb[i][j] += dpb[i+1][j]   \n",
    "\n",
    "        # 遍历\n",
    "        cross = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                size = min(dpl[i][j], dpr[i][j], dpt[i][j], dpb[i][j])\n",
    "                cross = max(cross, size)\n",
    "\n",
    "        return cross\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        if n==1:\n",
    "            if len(mines)==1:return 0\n",
    "            else:return 1\n",
    "        if n==2:\n",
    "            if len(mines)==4:return 0\n",
    "            else:return 1\n",
    "\n",
    "        #0~3分别表示左上右下方向上最大连续1的数值\n",
    "        dp=[[[1]*n for _ in range(n)] for _ in range(4)]\n",
    "        for ix,iy in mines:\n",
    "            for d in range(4):\n",
    "                dp[d][ix][iy]=0\n",
    "        res=0 if len(mines)==n**2 else 1\n",
    "\n",
    "        # 最边缘那一圈已经定死了 不会再改变了\n",
    "        # 先从左上角开始  仅看左上位置\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if dp[0][i][j] == 0:\n",
    "                    dp[1][i][j]=0\n",
    "                    dp[2][i][j]=0\n",
    "                    dp[3][i][j]=0\n",
    "                else:\n",
    "                    for d in range(4):\n",
    "                        dp[0][i][j]=dp[0][i][j-1]+1#左\n",
    "                        dp[1][i][j]=dp[1][i-1][j]+1#上\n",
    "\n",
    "        #从右下角开始  看向右与下两个方向\n",
    "        for i in range(n-2,0,-1):\n",
    "            for j in range(n-2,0,-1):\n",
    "                if dp[0][i][j] == 0:\n",
    "                    dp[1][i][j]=0\n",
    "                    dp[2][i][j]=0\n",
    "                    dp[3][i][j]=0\n",
    "                else:\n",
    "                    for d in range(4):\n",
    "                        dp[2][i][j]=dp[2][i][j+1]+1#右\n",
    "                        dp[3][i][j]=dp[3][i+1][j]+1#下\n",
    "                    Temp=min(dp[d][i][j] for d in range(4))\n",
    "                    res=max(res,Temp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        if n==1:\n",
    "            if len(mines)==1:return 0\n",
    "            else:return 1\n",
    "        if n==2:\n",
    "            if len(mines)==4:return 0\n",
    "            else:return 1\n",
    "\n",
    "        #0~3分别表示左上右下方向上最大连续1的数值\n",
    "        dp=[[[1]*n for _ in range(n)] for _ in range(4)]\n",
    "        for ix,iy in mines:\n",
    "            for d in range(4):\n",
    "                dp[d][ix][iy]=0\n",
    "        res=0 if len(mines)==n**2 else 1\n",
    "\n",
    "        # 最边缘那一圈已经定死了 不会再改变了\n",
    "        # 先从左上角开始  仅看左上位置\n",
    "        for i in range(1, n - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if dp[0][i][j] == 0:\n",
    "                    dp[1][i][j]=0\n",
    "                    dp[2][i][j]=0\n",
    "                    dp[3][i][j]=0\n",
    "                else:\n",
    "                    for d in range(4):\n",
    "                        dp[0][i][j]=dp[0][i][j-1]+1#左\n",
    "                        dp[1][i][j]=dp[1][i-1][j]+1#上\n",
    "\n",
    "        #从右下角开始  看向右与下两个方向\n",
    "        for i in range(n-2,0,-1):\n",
    "            for j in range(n-2,0,-1):\n",
    "                if dp[0][i][j] == 0:\n",
    "                    dp[1][i][j]=0\n",
    "                    dp[2][i][j]=0\n",
    "                    dp[3][i][j]=0\n",
    "                else:\n",
    "                    for d in range(4):\n",
    "                        dp[2][i][j]=dp[2][i][j+1]+1#右\n",
    "                        dp[3][i][j]=dp[3][i+1][j]+1#下\n",
    "                    Temp=min(dp[d][i][j] for d in range(4))\n",
    "                    res=max(res,Temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        # 定义dpx[i][j][k]为以[i,j]为中心，朝着方向x能延展的最大长度\n",
    "        dpl = [[1]*n for _ in range(n)] # 左\n",
    "        dpr = [[1]*n for _ in range(n)] # 右\n",
    "        dpt = [[1]*n for _ in range(n)] # 上\n",
    "        dpb = [[1]*n for _ in range(n)] # 下\n",
    "\n",
    "        # 把地雷坐标放上去\n",
    "        for mi, mj in mines:\n",
    "            dpl[mi][mj] = 0\n",
    "            dpr[mi][mj] = 0\n",
    "            dpt[mi][mj] = 0\n",
    "            dpb[mi][mj] = 0\n",
    "\n",
    "        # 计算左边和右边方向的长度\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                if dpl[i][j] != 0: dpl[i][j] += dpl[i][j-1]\n",
    "\n",
    "            for j in range(n-2, -1, -1):\n",
    "                if dpr[i][j] != 0: dpr[i][j] += dpr[i][j+1]\n",
    "\n",
    "        # 计算上面和下面方向的长度\n",
    "        for j in range(n):\n",
    "            for i in range(1, n):\n",
    "                if dpt[i][j] != 0: dpt[i][j] += dpt[i-1][j]\n",
    "\n",
    "            for i in range(n-2, -1, -1):\n",
    "                if dpb[i][j] != 0: dpb[i][j] += dpb[i+1][j]   \n",
    "\n",
    "        # 遍历\n",
    "        cross = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                size = min(dpl[i][j], dpr[i][j], dpt[i][j], dpb[i][j])\n",
    "                cross = max(cross, size)\n",
    "\n",
    "        return cross"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        down = [[0]*n for _ in range(n)]\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        right = [[0]*n for _ in range(n)]\n",
    "        zeroMemo = {(x, y) for x,y in mines}\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    left[r][c] = left[r][c-1] + 1 if c != 0 else 1\n",
    "                    down[r][c] = down[r-1][c] + 1 if r != 0 else 1\n",
    "        for r in range(n-1, -1, -1):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    up[r][c] = up[r+1][c] + 1 if r != n - 1 else 1\n",
    "                    right[r][c] = right[r][c+1] + 1 if c != n - 1 else 1\n",
    "        for k in range(ceil(n/2), 0, -1): # n等于3时，k最大为2\n",
    "            for r in range(k-1, n-k+1): # 当k等于2时，需要从(1,1)位置开始找,最大置为也只能为n-k\n",
    "                for c in range(k-1, n-k+1):\n",
    "                    if (r,c) in zeroMemo:\n",
    "                        continue\n",
    "                    if up[r][c] >= k and down[r][c] >= k and left[r][c] >= k and right[r][c] >= k:\n",
    "                        return k # 由于从大到小枚举，所以第一个答案即可以返回\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "       left = [[0] * n for _ in range(n)]\n",
    "       up = [[0] * n for _ in range(n)]\n",
    "       s = set()\n",
    "       for x, y in mines:\n",
    "          s.add((x, y))\n",
    "       for i in range(n):\n",
    "          for j in range(n):\n",
    "             if j == 0:\n",
    "                left[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                left[i][j] = 0 if (i, j) in s else left[i][j - 1] + 1\n",
    "             if i == 0:\n",
    "                up[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                up[i][j] = 0 if (i, j) in s else up[i - 1][j] + 1\n",
    "       res = 0\n",
    "       right = [[0] * n for _ in range(n)]\n",
    "       down = [[0] * n for _ in range(n)]\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          for j in range(n - 1, -1, -1):\n",
    "             if j == n - 1:\n",
    "                right[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                right[i][j] = 0 if (i, j) in s else right[i][j + 1] + 1\n",
    "             if i == n - 1:\n",
    "                down[i][j] = 1 if (i, j) not in s else 0\n",
    "             else:\n",
    "                down[i][j] = 0 if (i, j) in s else down[i + 1][j] + 1\n",
    "             res = max(res, min(min(left[i][j], right[i][j]), min(up[i][j], down[i][j])))\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        down = [[0]*n for _ in range(n)]\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        right = [[0]*n for _ in range(n)]\n",
    "        zeroMemo = {(x, y) for x,y in mines}\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    left[r][c] = left[r][c-1] + 1 if c != 0 else 1\n",
    "                    down[r][c] = down[r-1][c] + 1 if r != 0 else 1\n",
    "        # print(f\"left:{left}\")\n",
    "        # print(f\"down:{down}\")\n",
    "        for r in range(n-1, -1, -1):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    up[r][c] = up[r+1][c] + 1 if r != n - 1 else 1\n",
    "                    right[r][c] = right[r][c+1] + 1 if c != n - 1 else 1\n",
    "        # print(f\"up:{up}\")\n",
    "        # print(f\"right:{right}\")\n",
    "        for k in range(ceil(n/2), 0, -1):\n",
    "            for r in range(k-1, n):\n",
    "                for c in range(k-1, n):\n",
    "                    if (r,c) in zeroMemo:\n",
    "                        continue\n",
    "                    if up[r][c] >= k and down[r][c] >= k and left[r][c] >= k and right[r][c] >= k:\n",
    "                        return k\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        down = [[0]*n for _ in range(n)]\n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        right = [[0]*n for _ in range(n)]\n",
    "        zeroMemo = {(x, y) for x,y in mines}\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    left[r][c] = left[r][c-1] + 1 if c != 0 else 1\n",
    "                    down[r][c] = down[r-1][c] + 1 if r != 0 else 1\n",
    "        for r in range(n-1, -1, -1):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if (r,c) not in zeroMemo:\n",
    "                    up[r][c] = up[r+1][c] + 1 if r != n - 1 else 1\n",
    "                    right[r][c] = right[r][c+1] + 1 if c != n - 1 else 1\n",
    "        for k in range(ceil(n/2), 0, -1): # n等于3时，k最大为2\n",
    "            for r in range(k-1, n): # 当k等于2时，需要从(1,1)位置开始找\n",
    "                for c in range(k-1, n):\n",
    "                    if (r,c) in zeroMemo:\n",
    "                        continue\n",
    "                    if up[r][c] >= k and down[r][c] >= k and left[r][c] >= k and right[r][c] >= k:\n",
    "                        return k # 由于从大到小枚举，所以第一个答案即可以返回\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        up = [[0]*(n + 1) for _ in range(n)]\n",
    "        down = [[0]*(n + 1) for _ in range(n)]\n",
    "        left = [[0]*(n + 1) for _ in range(n)]\n",
    "        right = [[0]*(n + 1) for _ in range(n)]\n",
    "        \n",
    "        _set = set()\n",
    "        for x,y in mines:\n",
    "            _set.add((x,y))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                left[i][j + 1] = 0 if (i,j) in _set else left[i][j] + 1\n",
    "                up[i][j + 1] = 0 if (j,i) in _set else up[i][j] + 1\n",
    "            for j in range(n - 1,0,-1):\n",
    "                right[i][j] = 0 if (i,j) in _set else right[i][j + 1] + 1\n",
    "                down[i][j] = 0 if (j,i) in _set else down[i][j + 1] + 1\n",
    "        if len(_set) == n*n:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(1,n - 1):\n",
    "            for j in range(1,n - 1):\n",
    "                if (i,j) not in _set:\n",
    "                    ans = max(ans,min(up[j][i],down[j][i] - 1,left[i][j],right[i][j] - 1))\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "\n",
    "        mineSet = set()\n",
    "        for mine in mines:\n",
    "            mineSet.add(tuple(mine))\n",
    "\n",
    "\n",
    "        l = [[0]*n for _ in range(n)]\n",
    "        r = [[0]*n for _ in range(n)]\n",
    "        b = [[0]*n for _ in range(n)]\n",
    "        t = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            l[i][0] = 1 if (i,0) not in mineSet else 0\n",
    "            for j in range(1, n):\n",
    "                l[i][j] = l[i][j-1] + 1 if (i,j) not in mineSet else 0\n",
    "\n",
    "            r[i][n-1] = 1 if (i,n-1) not in mineSet else 0\n",
    "            for j in range(n-2, -1, -1):\n",
    "                r[i][j] = r[i][j+1] + 1 if (i,j) not in mineSet else 0\n",
    "\n",
    "        for j in range(n):\n",
    "            t[0][j] = 1 if (0,j) not in mineSet else 0\n",
    "            for i in range(1,n):\n",
    "                t[i][j] = t[i-1][j] + 1 if (i,j) not in mineSet else 0\n",
    "\n",
    "            b[n-1][j] = 1 if (n-1, j) not in mineSet else 0\n",
    "            for i in range(n-2, -1, -1):\n",
    "                b[i][j] = b[i+1][j] + 1 if (i,j) not in mineSet else 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res = max(res, min(l[i][j], r[i][j], b[i][j], t[i][j]))\n",
    "        return res\n",
    "\n",
    "        # print(l)\n",
    "        # print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        mines = set((x, y) for x, y in mines)\n",
    "\n",
    "        left = []\n",
    "        for i in range(n):\n",
    "            row = [0]\n",
    "            for j in range(n):\n",
    "                row.append(row[-1] + 1 if (i, j) not in mines else 0)\n",
    "            left.append(row[1:])\n",
    "\n",
    "        right = []\n",
    "        for i in range(n):\n",
    "            row = [0]\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                row.append(row[-1] + 1 if (i, j) not in mines else 0)\n",
    "            right.append(row[1:][::-1])\n",
    "\n",
    "        up = []\n",
    "        t = [0] * n\n",
    "        for i in range(n):\n",
    "            row = []\n",
    "            for j in range(n):\n",
    "                row.append(t[j] + 1 if (i, j) not in mines else 0)\n",
    "            t = row\n",
    "            up.append(row)\n",
    "\n",
    "        down = []\n",
    "        t = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            row = []\n",
    "            for j in range(n):\n",
    "                row.append(t[j] + 1 if (i, j) not in mines else 0)\n",
    "            t = row\n",
    "            down.insert(0, row)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, min(left[i][j], right[i][j], up[i][j], down[i][j])) \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        nums=[[1]*n for i in range(n)]\n",
    "        for i,j in mines:\n",
    "            nums[i][j]=0\n",
    "        left=[[0]*n for i in range(n)]\n",
    "        right=[[0]*n for i in range(n)]\n",
    "        up=[[0]*n for i in range(n)]\n",
    "        down=[[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if nums[i][0]==1:\n",
    "                left[i][0]=1\n",
    "            if nums[i][-1]==1:\n",
    "                right[i][-1]=1\n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                if nums[i][j]==1:\n",
    "                    left[i][j]=left[i][j-1]+1\n",
    "        for i in range(n):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if nums[i][j]==1:\n",
    "                    right[i][j]=right[i][j+1]+1\n",
    "        up[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                if nums[i][j]==1:\n",
    "                    up[i][j]=up[i-1][j]+1\n",
    "        down[-1]=nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n):\n",
    "                if nums[i][j]==1:\n",
    "                    down[i][j]=down[i+1][j]+1\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if nums[i][j]==1:\n",
    "                    res=max(res,min(left[i][j],right[i][j],up[i][j],down[i][j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        #不难想到图形DP对吧\n",
    "        #left[i]表示当前这点延申到左边的最长连续1个数\n",
    "        #其他三个方向是同理的\n",
    "        grid=[[1]*n for _ in range(n)]\n",
    "        for u,v in mines:\n",
    "            grid[u][v]=0\n",
    "        left=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            pre=0\n",
    "            for j in range(n):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                left[i][j]=pre\n",
    "        right=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            pre=0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                right[i][j]=pre\n",
    "        up=[[0]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(n):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                up[i][j]=pre\n",
    "        down=[[0]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                down[i][j]=pre\n",
    "        #汇总考虑答案\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans=max(ans,min(left[i][j],right[i][j],up[i][j],down[i][j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1]*n for _ in range(n)]\n",
    "        for x,y in mines:\n",
    "            grid[x][y] = 0 \n",
    "        # 表示以i结尾i的上面有多少个连续的1 \n",
    "        dpu = [[0]*n for _ in range(n)]\n",
    "        dpd = [[0]*n for _ in range(n)]\n",
    "        dpl = [[0]*n for _ in range(n)]\n",
    "        dpr = [[0]*n for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):    \n",
    "            if grid[i][0] == 1:\n",
    "                dpl[i][0] = 1 \n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                dpu[0][j] = 1\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            if grid[i][len(grid[0])-1] == 1:\n",
    "                dpr[i][len(grid[0])-1] = 1\n",
    "\n",
    "        for j in range(n-1,-1,-1):\n",
    "            if grid[len(grid)-1][j] == 1:\n",
    "                dpd[len(grid)-1][j] = 1 \n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dpl[i][j] = dpl[i][j-1] + 1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dpu[i][j] = dpu[i-1][j] + 1\n",
    "                    \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j] != 0:\n",
    "                    dpr[i][j] = dpr[i][j+1] + 1\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j] != 0:\n",
    "                    dpd[i][j] = dpd[i+1][j] + 1\n",
    "        \n",
    "        # for i in grid:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # for i in dpu:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # for i in dpd:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # for i in dpl:\n",
    "        #     print(i)\n",
    "        # print()\n",
    "        # for i in dpr:\n",
    "        #     print(i)\n",
    "\n",
    "        res = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res = max(res,min(dpd[i][j],dpl[i][j],dpr[i][j],dpu[i][j]))\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        g = [[1] * (n+2) for _ in range(n+2)]\n",
    "        for x, y in mines:\n",
    "            g[x+1][y+1] = 0\n",
    "        l, r, u, d = [[0] * (n+2) for _ in range(n+2)], [[0] * (n+2) for _ in range(n+2)], [[0] * (n+2) for _ in range(n+2)], [[0] * (n+2) for _ in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if g[i][j]:\n",
    "                    r[i][j], d[i][j] = r[i-1][j] + 1, d[i][j-1] + 1\n",
    "                if g[n+1-i][n+1-j]:\n",
    "                    l[n+1-i][n+1-j], u[n+1-i][n+1-j] = l[n+2-i][n+1-j] + 1, u[n+1-i][n+2-j] + 1\n",
    "        return max(min(l[i][j],r[i][j],u[i][j],d[i][j]) for i in range(1,n+1) for j in range(1,n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        #图形DP是吧\n",
    "        #left[i]表示当前这点延申到左边的最长连续1个数\n",
    "        #其他三个方向是同理的\n",
    "        grid=[[1]*n for _ in range(n)]\n",
    "        for u,v in mines:\n",
    "            grid[u][v]=0\n",
    "        left=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            pre=0\n",
    "            for j in range(n):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                left[i][j]=pre\n",
    "        right=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            pre=0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                right[i][j]=pre\n",
    "        up=[[0]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(n):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                up[i][j]=pre\n",
    "        down=[[0]*n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if grid[i][j]: pre+=1\n",
    "                else: pre=0\n",
    "                down[i][j]=pre\n",
    "        #汇总考虑答案\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans=max(ans,min(left[i][j],right[i][j],up[i][j],down[i][j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1] * n for _ in range(n)]\n",
    "\n",
    "        for x, y in mines:\n",
    "            grid[x][y] = 0\n",
    "        \n",
    "        left = [[0] * n for _ in range(n)]\n",
    "        right = [[0] * n for _ in range(n)]\n",
    "        up = [[0] * n for _ in range(n)]\n",
    "        down = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    left[i][j] = left[i][j - 1] + 1 if j > 0 else 1\n",
    "                    up[i][j] = up[i - 1][j] + 1 if i > 0 else 1\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    right[i][j] = right[i][j + 1] + 1 if j < n - 1 else 1\n",
    "                    down[i][j] = down[i + 1][j] + 1 if i < n - 1 else 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    size = min(left[i][j], right[i][j], up[i][j], down[i][j])\n",
    "                    res = max(res, size)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        g = [[1] * (n+2) for _ in range(n+2)]\n",
    "        for i,j in mines:\n",
    "            g[i+1][j+1] = 0\n",
    "        # display(pd.DataFrame(g))\n",
    "\n",
    "        a = [[0]*(n+2) for _ in range(n+2)]\n",
    "        b = [[0]*(n+2) for _ in range(n+2)]\n",
    "        c = [[0]*(n+2) for _ in range(n+2)]\n",
    "        d = [[0]*(n+2) for _ in range(n+2)]\n",
    "\n",
    "        # 从左到右，从上到下\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if g[i][j] == 1:\n",
    "                    a[i][j] = a[i-1][j]+1\n",
    "                    b[i][j] = b[i][j-1]+1\n",
    "        # 从右到左，从下到上\n",
    "        for i in range(n,0,-1):\n",
    "            for j in range(n,0,-1):\n",
    "                if g[i][j] == 1:\n",
    "                    c[i][j] = c[i+1][j]+1\n",
    "                    d[i][j] = d[i][j+1]+1\n",
    "        # display(pd.DataFrame(a))\n",
    "        # display(pd.DataFrame(b))\n",
    "        # display(pd.DataFrame(c))\n",
    "        # display(pd.DataFrame(d))\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                ans_i = min([a[i][j],b[i][j],c[i][j],d[i][j]])\n",
    "                ans = max([ans,ans_i])\n",
    "        return(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "\n",
    "        m = [[1]*n for _ in range(n)]\n",
    "        for x,y in mines:\n",
    "            m[x][y] = 0\n",
    "        \n",
    "        left = [[0]*n for _ in range(n)]\n",
    "        right = [[0]*n for _ in range(n)]\n",
    "        up = [[0]*n for _ in range(n)]\n",
    "        down = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1):\n",
    "                if m[i][j]:\n",
    "                    left[i][j + 1] = 1 + left[i][j]\n",
    "                if m[j][i]:\n",
    "                    up[j + 1][i] = 1 + up[j][i]\n",
    "                if m[i][n - 1 - j]:\n",
    "                    right[i][n - 2 - j] = 1 + right[i][n - 1 - j]\n",
    "                if m[n - 1 - j][i]:\n",
    "                    down[n - 2 - j][i] = 1 + down[n - 1 - j][i]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if m[i][j]:\n",
    "                    ans = max(ans,1 + min(up[i][j],left[i][j],right[i][j],down[i][j]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1]*n for _ in range(n)]\n",
    "        for x,y in mines:\n",
    "            grid[x][y] = 0\n",
    "        left,right,up,down = [[0]*n for _ in range(n)],[[0]*n for _ in range(n)],[[0]*n for _ in range(n)],[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j-1] == 1:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "        for i in range(n):\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j+1] == 1:\n",
    "                    right[i][j] = right[i][j+1] + 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                if grid[i-1][j] == 1:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n):\n",
    "                if grid[i+1][j] == 1:\n",
    "                    down[i][j] = down[i+1][j] + 1\n",
    "        #print(len(mines),n*n)\n",
    "        res = 0\n",
    "        #print(up,down,left,right)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res,min(up[i][j],down[i][j],left[i][j],right[i][j]))\n",
    "        if res > 0:\n",
    "            return res + 1\n",
    "        if len(mines) < n*n:\n",
    "            res = 1\n",
    "        else:\n",
    "            res = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        g = [[1] * (n+2) for _ in range(n+2)]\n",
    "\n",
    "        for x, y in mines:\n",
    "            g[x+1][y+1] = 0\n",
    "\n",
    "        a, b, c, d = [[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if g[i][j] == 1:\n",
    "                    # a[i][j] = a[i-1][j] + 1\n",
    "                    # b[i][j] = a[i][j-1] + 1\n",
    "                    a[i][j] = a[i - 1][j] + 1\n",
    "                    b[i][j] = b[i][j - 1] + 1\n",
    "                if g[n+1-i][n+1-j] == 1:\n",
    "                    c[n+1-i][n+1-j] = c[n+2-i][n+1-j] + 1\n",
    "                    d[n+1-i][n+1-j] = d[n+1-i][n+2-j] + 1\n",
    "        # for i in range(1, n + 1):\n",
    "        #     for j in range(1, n + 1):\n",
    "        #         if g[i][j] == 1:\n",
    "        #             a[i][j] = a[i - 1][j] + 1\n",
    "        #             b[i][j] = b[i][j - 1] + 1\n",
    "        #         if g[n + 1 - i][n + 1 - j] == 1:\n",
    "        #             c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1\n",
    "        #             d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1): \n",
    "                res = max(res, min(a[i][j], b[i][j], c[i][j], d[i][j]))\n",
    "                # res = max(res, min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines):\n",
    "        quanyi = [1]*n\n",
    "       \n",
    "        juzhen=[]\n",
    "        for i in range(n):\n",
    "            juzhen.append(quanyi.copy())\n",
    "        for i in mines:\n",
    "            juzhen[i[0]][i[1]]=0\n",
    "        print(juzhen,22222)\n",
    "        zuobian =[ [0]*n  for i in range(n)]\n",
    "        youbian= [ [0]*n  for i in range(n)]\n",
    "        shangmian = [ [0]*n  for i in range(n)]\n",
    "        xiamian =[ [0]*n  for i in range(n)]\n",
    "        zuobian[0][0]=1515\n",
    "        print(juzhen)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if juzhen[i][j]==0:\n",
    "                    zuobian[i][j]=0\n",
    "                    shangmian[i][j]=0\n",
    "                else:\n",
    "                    if j>0:\n",
    "                        zuobian[i][j] = zuobian[i][j-1]+1\n",
    "                    else:\n",
    "                        print(i, j)\n",
    "                        zuobian[i][j]=juzhen[i][j]\n",
    "                    if i>0:\n",
    "                        shangmian[i][j] = shangmian[i-1][j]+1\n",
    "                    else:\n",
    "                        shangmian[i][j]=juzhen[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                i_ = n-1-i\n",
    "                j_ = n-1-j\n",
    "                if juzhen[i_][j_]==0:\n",
    "                    youbian[i_][j_]=0\n",
    "                    xiamian[i_][j_]=0\n",
    "                else:\n",
    "                    if j_<n-1:\n",
    "                       \n",
    "                        youbian[i_][j_] = youbian[i_][j_+1]+1\n",
    "                    else:\n",
    "                        youbian[i_][j_]=juzhen[i_][j_]\n",
    "                    if i_<n-1:\n",
    "                        xiamian[i_][j_] =xiamian[i_+1][j_]+1\n",
    "                    else:\n",
    "                        xiamian[i_][j_] = juzhen[i_][j_]\n",
    "        res=-1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                temp=[]\n",
    "                temp.append(shangmian[i][j])\n",
    "                temp.append(xiamian[i][j])\n",
    "                temp.append(zuobian[i][j])\n",
    "                temp.append(youbian[i][j])\n",
    "                if min(temp)> res:\n",
    "                    res= min(temp)\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        if n == 1 and mines == [[0, 0]]:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1 if len(mines) < 4 else 0\n",
    "            \n",
    "        mp = [[1] * n for _ in range(n)]\n",
    "        for mine in mines:\n",
    "            mp[mine[0]][mine[1]] = 0\n",
    "\n",
    "        ups = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                if mp[i][j] == 0 or mp[i-1][j] == 0:\n",
    "                    continue\n",
    "                ups[i][j] = ups[i-1][j] + 1\n",
    "\n",
    "        downs = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(n):\n",
    "                if mp[i][j] == 0 or mp[i+1][j] == 0:\n",
    "                    continue\n",
    "                downs[i][j] = downs[i+1][j] + 1\n",
    "\n",
    "        lefts = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                if mp[i][j] == 0 or mp[i][j-1] == 0:\n",
    "                    continue\n",
    "                lefts[i][j] = lefts[i][j-1] + 1\n",
    "\n",
    "        rights = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n-2, -1, -1):\n",
    "                if mp[i][j] == 0 or mp[i][j+1] == 0:\n",
    "                    continue\n",
    "                rights[i][j] = rights[i][j+1] + 1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(1, n-1):\n",
    "                if mp[i][j] == 0:\n",
    "                    continue\n",
    "                k = min(ups[i][j], downs[i][j], lefts[i][j], rights[i][j]) + 1\n",
    "                res = max(res, k)\n",
    "                mp[i][j] = k\n",
    "        \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        dp_left = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dp_right = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dp_top = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dp_bottom = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        matrix = [[1 for _ in range(n)] for _ in range(n)]\n",
    "        for m in mines:\n",
    "            matrix[m[0]][m[1]] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j-1] == 0:\n",
    "                    dp_left[i][j] = 0\n",
    "                else:\n",
    "                    dp_left[i][j] = dp_left[i][j-1] + 1\n",
    "        for i in range(n):\n",
    "            for j in range(n-2, -1, -1):\n",
    "                if matrix[i][j+1] == 0:\n",
    "                    dp_right[i][j] = 0\n",
    "                else:\n",
    "                    dp_right[i][j] = dp_right[i][j+1] + 1   \n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                if matrix[i-1][j] == 0:\n",
    "                    dp_top[i][j] = 0\n",
    "                else:\n",
    "                    dp_top[i][j] = dp_top[i-1][j] + 1  \n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(n):\n",
    "                if matrix[i+1][j] == 0:\n",
    "                    dp_bottom[i][j] = 0\n",
    "                else:\n",
    "                    dp_bottom[i][j] = dp_bottom[i+1][j] + 1   \n",
    "\n",
    "        max_result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    max_result = max(max_result, min(dp_left[i][j], dp_right[i][j], dp_top[i][j], dp_bottom[i][j]) + 1)\n",
    "        return max_result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        grid = [[1 for _ in range(n)] for _ in range(n)]\n",
    "        left = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        right = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        top = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        bottom = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for x,y in mines:\n",
    "            grid[x][y] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                top[i][j] = grid[i][j]\n",
    "                left[i][j] = grid[i][j]\n",
    "                if grid[i][j] == 1 and i:\n",
    "                    top[i][j] += top[i-1][j]\n",
    "                if grid[i][j] == 1 and j:\n",
    "                    left[i][j] += left[i][j-1]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                right[i][j] = grid[i][j]\n",
    "                bottom[i][j] = grid[i][j]\n",
    "                if grid[i][j] == 1 and i < n-1:\n",
    "                    bottom[i][j] += bottom[i+1][j]\n",
    "                if grid[i][j] == 1 and j < n-1:\n",
    "                    right[i][j] += right[i][j+1]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res = min(min(left[i][j], right[i][j]), min(top[i][j], bottom[i][j]))\n",
    "                ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        s = set((x,y) for x, y in mines)\n",
    "        f = [[[0] * n for _ in range(n)] for _ in range(4)]\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in s:\n",
    "                    g[i][j] = 1\n",
    "        # print(f'{g}')\n",
    "        for i in range(n):\n",
    "            left, right = 0, 0\n",
    "            for j in range(n):\n",
    "                left = (left + 1) if g[i][j] else 0\n",
    "                f[0][i][j] = left\n",
    "                right = (right + 1) if g[i][n - 1 - j] else 0\n",
    "                f[1][i][n - 1 - j] = right\n",
    "        for i in range(n):\n",
    "            up, down = 0, 0\n",
    "            for j in range(n):\n",
    "                up = (up + 1) if g[j][i] else 0\n",
    "                f[2][j][i] = up\n",
    "                down = (down + 1) if g[n - 1 - j][i] else 0\n",
    "                f[3][n - 1 - j][i] = down\n",
    "        # print(f'{f[2],f[3]}')\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mn = min(f[k][i][j] for k in range(4))\n",
    "                if mn > ans:\n",
    "                    ans = mn\n",
    "                    # print(f'{i, j}')\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        mines = set([tuple(mine) for mine in mines])\n",
    "        left, right, up, down = [[0] * n for _ in range(n)], [[0] * n for _ in range(n)], [[0] * n for _ in range(n)], [\n",
    "            [0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in mines:\n",
    "                    left[i][j] = left[i][j - 1] + 1 if j > 0 else 1\n",
    "                    up[i][j] = up[i - 1][j] + 1 if i > 0 else 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if (i, j) not in mines:\n",
    "                    right[i][j] = right[i][j + 1] + 1 if j < n - 1 else 1\n",
    "                    down[i][j] = down[i + 1][j] + 1 if i < n - 1 else 1\n",
    "        return max([min(left[i][j], right[i][j], up[i][j], down[i][j]) for i in range(n) for j in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        g = [[1] * (n + 10) for _ in range(n + 10)]\n",
    "        for x, y in mines:\n",
    "            g[x + 1][y + 1] = 0\n",
    "        a, b, c, d = [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)], [[0] * (n + 10) for _ in range(n + 10)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if g[i][j] == 1:\n",
    "                    a[i][j] = a[i - 1][j] + 1\n",
    "                    b[i][j] = b[i][j - 1] + 1\n",
    "                if g[n + 1 - i][n + 1 - j] == 1:\n",
    "                    c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1\n",
    "                    d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                ans = max(ans, min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        g = [[1] * (n+2) for _ in range(n+2)]\n",
    "\n",
    "        for x, y in mines:\n",
    "            g[x+1][y+1] = 0\n",
    "\n",
    "        a, b, c, d = [[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)],[[0] * (n+2) for _ in range(n+2)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if g[i][j] == 1:\n",
    "                    a[i][j] = a[i-1][j] + 1\n",
    "                    b[i][j] = a[i][j-1] + 1\n",
    "                if g[n+1-i][n+1-j] == 1:\n",
    "                    c[n+1-i][n+1-j] = c[n+2-i][n+1-j] + 1\n",
    "                    d[n+1-i][n+1-j] = d[n+1-i][n+2-j] + 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if g[i][j] == 1:\n",
    "                    a[i][j] = a[i - 1][j] + 1\n",
    "                    b[i][j] = b[i][j - 1] + 1\n",
    "                if g[n + 1 - i][n + 1 - j] == 1:\n",
    "                    c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1\n",
    "                    d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1): \n",
    "                res = max(res, min(a[i][j], b[i][j], c[i][j], d[i][j]))\n",
    "                # res = max(res, min(min(a[i][j], b[i][j]), min(c[i][j], d[i][j])))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        if len(mines) == n**2:\n",
    "            return 0\n",
    "\n",
    "        dp = [[1] * n for _ in range(n)]\n",
    "        left = dp.copy()\n",
    "        right = dp.copy()\n",
    "        bottom = dp.copy()\n",
    "        top = dp.copy()\n",
    "\n",
    "        for r, c in mines:\n",
    "            dp[r][c] = 0\n",
    "            left[r][c] = 0\n",
    "            right[r][c] = 0\n",
    "            bottom[r][c] = 0\n",
    "            top[r][c] = 0\n",
    "\n",
    "        def count(a, b):\n",
    "            return a + b if b else 0\n",
    "\n",
    "        left = [list(accumulate(row, func=count)) for row in left]\n",
    "        right = [list(accumulate(row[::-1], func=count))[::-1] for row in right]\n",
    "        top = zip(*top)\n",
    "        top = list(zip(*[accumulate(row, func=count) for row in top]))\n",
    "        bottom = zip(*bottom)\n",
    "        bottom = list(zip(*[list(accumulate(row[::-1], func=count))[::-1] for row in bottom]))\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(1,n-1):\n",
    "                if dp[i][j]:\n",
    "                    dp[i][j] = 1 + min(top[i-1][j], bottom[i+1][j]\n",
    "                    , left[i][j-1], right[i][j+1])\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        \n",
    "        # print(dp)\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(top)\n",
    "        # print(bottom)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        matrix = [[[1, 1, 1, 1] for _ in range(n)] for _ in range(n)]\n",
    "        for i, j in mines:\n",
    "            matrix[i][j] = [0, 0, 0, 0]\n",
    "        # 0, 1左和上\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j][0] == 0:\n",
    "                    continue\n",
    "                matrix[i][j][0] = matrix[i][j - 1][0] + 1\n",
    "                matrix[i][j][1] = matrix[i - 1][j][1] + 1\n",
    "\n",
    "        # 2, 3右和下\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if matrix[i][j][0] == 0:\n",
    "                    continue\n",
    "                matrix[i][j][2] = matrix[i][j + 1][2] + 1\n",
    "                matrix[i][j][3] = matrix[i + 1][j][3] + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, min(matrix[i][j]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        zero_set = set(map(tuple, mines))\n",
    "        # f[i][j][0/1/2/3]表示以(i,j)为起点往左/上/右/下方向上1的最大连续长度\n",
    "        f = [[[0] * 4 for _ in range(n)] for _ in range(n)]\n",
    "        # 左 / 上\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in zero_set:\n",
    "                    f[i][j][0] = 1 + (f[i-1][j][0] if i-1 >= 0 else 0)\n",
    "                    f[i][j][1] = 1 + (f[i][j-1][1] if j-1 >= 0 else 0)\n",
    "        # 右 / 下\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if (i, j) not in zero_set:\n",
    "                    f[i][j][2] = 1 + (f[i+1][j][2] if i+1 < n else 0)\n",
    "                    f[i][j][3] = 1 + (f[i][j+1][3] if j+1 < n else 0)\n",
    "        # 遍历得到结果\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, min(f[i][j]))\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        seen = set(tuple(m) for m in mines)\n",
    "\n",
    "        dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        # 0: up, 1:down,2:left, 3:right\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # left\n",
    "                if (i, j) in seen:\n",
    "                    continue\n",
    "                if j - 1 >= 0:\n",
    "                    dp[i][j][2] = dp[i][j - 1][2] + 1\n",
    "                else:\n",
    "                    dp[i][j][2] = 1\n",
    "                \n",
    "                if i - 1 >= 0:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                else:\n",
    "                    dp[i][j][0] = 1\n",
    "\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                # right\n",
    "\n",
    "                if (i, j) in seen:\n",
    "                    continue\n",
    "                if j + 1 <= n - 1:\n",
    "                    dp[i][j][3] = dp[i][j + 1][3] + 1\n",
    "                else:\n",
    "                    dp[i][j][3] = 1\n",
    "                \n",
    "                if i + 1 <= n - 1:\n",
    "                    dp[i][j][1] = dp[i + 1][j][1] + 1\n",
    "                else:\n",
    "                    dp[i][j][1] = 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) in seen:\n",
    "                    continue\n",
    "                \n",
    "                res = max(res, min(dp[i][j]))\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        max_extension = [[[0, 0, 0, 0] for i in range(n)] for j in range(n)]\n",
    "        mines_set = set([(x[0], x[1]) for x in mines])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) in mines_set:\n",
    "                    max_extension[i][j][0] = 0\n",
    "                    max_extension[i][j][1] = 0\n",
    "                else:\n",
    "                    if i == 0:\n",
    "                        max_extension[i][j][1] = 1\n",
    "                    else:\n",
    "                        max_extension[i][j][1] = max_extension[i-1][j][1]+1\n",
    "                    if j == 0:\n",
    "                        max_extension[i][j][0] = 1\n",
    "                    else:\n",
    "                        max_extension[i][j][0] = max_extension[i][j-1][0]+1\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if (i, j) in mines_set:\n",
    "                    max_extension[i][j][2] = 0\n",
    "                    max_extension[i][j][3] = 0\n",
    "                else:\n",
    "                    if i == n-1:\n",
    "                        max_extension[i][j][2] = 1\n",
    "                    else:\n",
    "                        max_extension[i][j][2] = max_extension[i+1][j][2]+1\n",
    "                    if j == n-1:\n",
    "                        max_extension[i][j][3] = 1\n",
    "                    else:\n",
    "                        max_extension[i][j][3] = max_extension[i][j+1][3]+1\n",
    "        \n",
    "        # for i in range(4):\n",
    "        #     for j in range(n):\n",
    "        #         for k in range(n):\n",
    "        #             print(max_extension[j][k][i], end = ',')\n",
    "        #         print()\n",
    "        #     print('\\n')\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if min(max_extension[i][j]) > res:\n",
    "                    res = min(max_extension[i][j])\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n",
    "        zeros = set()\n",
    "        for mine in mines:\n",
    "            zeros.add((mine[0], mine[1]))\n",
    "        dp = [[[0, 0, 0, 0] for _ in range(n + 2)] for _ in range(n + 2)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if (i, j) in zeros:\n",
    "                    dp[i + 1][j + 1] = [0, 0, 0, 0]\n",
    "                else:\n",
    "                    dp[i + 1][j + 1][0] = dp[i + 1][j][0] + 1\n",
    "                    dp[i + 1][j + 1][1] = dp[i][j + 1][1] + 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if (i, j) in zeros:\n",
    "                    dp[i + 1][j + 1] = [0, 0, 0, 0]\n",
    "                else:\n",
    "                    dp[i + 1][j + 1][2] = dp[i + 1][j + 2][2] + 1\n",
    "                    dp[i + 1][j + 1][3] = dp[i + 2][j + 1][3] + 1\n",
    "        # print(dp)                    \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # if res < min(dp[i + 1][j + 1]):\n",
    "                #     res = min(dp[i + 1][j + 1])\n",
    "                #     if min(dp[i + 1][j + 1]) == 3:\n",
    "                #         print(i, j, dp[i + 1][j + 1])\n",
    "                res = max(res, min(dp[i + 1][j + 1]))\n",
    "\n",
    "        return res\n",
    "\n",
    "                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
